package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;

/**
 * 向有序链表中插入一个节点
 * @author zifangsky
 *
 */
public class Problem_005_InsertIntoSortedList {

	/**
	 * 向有序链表中插入一个节点
	 * 
	 * @时间复杂度 O(n)
	 * @param headNode
	 * @param newNode
	 * @return
	 */
	public SinglyNode<Integer> insertIntoSortedList(SinglyNode<Integer> headNode,SinglyNode<Integer> newNode){
		if(newNode.getData() <= headNode.getData()){
			newNode.setNext(headNode);
			return newNode;
		}else{
			SinglyNode currentNode=headNode;
			while(currentNode.getNext() != null && newNode.getData() > ((SinglyNode<Integer>)currentNode.getNext()).getData()){
				currentNode = currentNode.getNext();
			}
			newNode.setNext(currentNode.getNext());
			currentNode.setNext(newNode);
	
			return headNode;
		}
	}
	
	@Test
	public void testMethods(){
		SinglyNode headNode = new SinglyNode(11);
		
		SinglyNode currentNode = headNode;
		for(int i=2;i<=5;i++){
			SinglyNode tmpNode = new SinglyNode(11 * i);
			currentNode.setNext(tmpNode);
			currentNode = tmpNode;
		}
		
		//遍历初始链接
		SinglyNodeOperations.print(headNode);
		
		SinglyNode newNode = new SinglyNode(66);
		headNode = insertIntoSortedList(headNode, newNode);

		//遍历最终结果
		SinglyNodeOperations.print(headNode);
	}
	
	
}
